package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 738.单调递增的数字
 *
 * @author cg
 * @program LeetCode->LeetCode_738
 * @create 2022-09-09 11:17
 **/
public class LeetCode_738 {

    @Test
    public void test738() {
        System.out.println(monotoneIncreasingDigits(10));
        System.out.println(monotoneIncreasingDigits(1234));
        System.out.println(monotoneIncreasingDigits(332));
        System.out.println(monotoneIncreasingDigits(100));
        System.out.println(monotoneIncreasingDigits(101));
    }

    /**
     * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
     * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
     * <p>
     * 示例 1:
     * 输入: n = 10
     * 输出: 9
     * <p>
     * 示例 2:
     * 输入: n = 1234
     * 输出: 1234
     * <p>
     * 示例 3:
     * 输入: n = 332
     * 输出: 299
     * <p>
     * 提示:
     * 0 <= n <= 10^9
     *
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        String[] arr = (n + "").split("");
        int start = arr.length;
        for (int i = arr.length - 1; i > 0; i--) {
            if (Integer.parseInt(arr[i]) < Integer.parseInt(arr[i - 1])) {
                arr[i - 1] = Integer.parseInt(arr[i - 1]) - 1 + "";
                start = i;
            }
        }
        for (int i = start; i < arr.length; i++) {
            arr[i] = "9";
        }
        return Integer.parseInt(String.join("", arr));
    }

}
